面向在线广告全链路拍卖机制设计新突破 — Two-stage Auction

丨目录：

   · 背景

   · 问题定义

   · 传统解法次优性分析

   · 粗选阶段设计

   · 实验结果

   · 结论

   · 参考文献

针对工业界广告系统中广泛存在的多阶段系统，我们研究两阶段广告拍卖机制设计这一新颖问题。在考虑机器学习模型和优化问题在两阶段之间的相互关系的情况下，设计了基于广告粒度的子集选择指标，称为粗选得分，及其相应的可扩展近似算法。并基于此提出了两阶段拍卖满足激励兼容的经济学性质。相较于现在广泛应用的忽略两阶段关系的贪心两阶段广告拍卖设计，在社会福利和收入上均有提升。我们提出的方案被 TheWebConf 2022 收录，并且该方案得到了Google Research 的关注，在其最新的工作中沿用两阶段拍卖机制的设计思路。

论文：On Designing a Two-stage Auction for Online Advertising

下载：https://arxiv.org/abs/2111.05555

▐ 背景

为了保证广告平台市场效率，即让正确的广告投放给正确的用户，广告拍卖机制需要综合考虑广告主的出价，以及广告和用户的展示质量。比如，在广泛使用的广义二价（generalized second price, GSP）拍卖中，广告位的分配就是根据广告主的出价乘上广告的展示质量。广告展示质量通常使用用户在看到广告后的潜在行为的概率，比如点击率（click through rate, CTR）来衡量。于是广告拍卖的表现不仅取决于拍卖机制本身，还取决于用于评估广告展示质量的机器学习模型的准确性。

在实际工业应用中，因为直接实现一个一阶段的广告拍卖机制会遇到扩展性的难题，所以通常使用两阶段的拍卖架构来实现系统扩展性和拍卖表现之间的平衡。一阶段的广告拍卖机制需要在几十毫秒之内决定广告位在一个由上千广告构成的候选集上面的分配和收费。然而，复杂的学习模型，比如 Wide&Deep 和 DIN 无法做到在如此短的时间限制之内完成对整个候选集合所有广告的 CTR 预测计算。为了减轻广告拍卖优化性能和系统扩展性之间的两难问题，现代拍卖系统使用的两阶段架构在大规模在线推荐系统中也是广泛使用的。一种直接的类似贪心思想的两阶段拍卖设计展示在图 1a 中：在第一阶段，称为粗选阶段（pre-auction），该方法使用一个粗糙而快速的点击率预估模型 对候选全集 中的所有广告计算其粗糙的点击率 ，并使用广告主的出价乘以粗糙点击率来排序选择前 个广告构成子集 传给第二阶段；然后第二阶段，称为拍卖阶段（auction），使用精细而复杂的点击率预估模型 来对子集 的广告进行预估，并执行 GSP 拍卖。这种在两个阶段都使用点击率预估计算期望点击价值进行排序贪心选择的方案在工业界中有广泛的应用，但它存在拍卖分配效率的损失。有的广告如果能够进入第二阶段，其实会得到较高的精细点击率并最终赢得一个广告位，但是由于其在第一阶段的点击率较低而被淘汰所以无法获得这个本来适合它的广告位。

上述提到的两阶段拍卖的贪心设计实际上反映了将两阶段架构应用于在线广告的一个常见误区。当在两阶段拍卖中优化拍卖效果的时候，只是把每个阶段单独看作原始优化问题改变了问题规模的版本，然后独立使用同样的评估指标进行选择，会使得最终两阶段拍卖的效果受到损失。拍卖的设计者应该考虑两个阶段之间的相互关系，即第二阶段会在第一阶段选择的子集上进行更加精细的预估和决策，从而对两个阶段进行适当的解耦和找到适当的优化问题。

▐ 问题定义

一阶段广告拍卖机制

在线广告最常用的机制之一是广义二价拍卖（generalized second price, GSP）机制。给定每个广告主 对于一次广告点击的出价 ，以及广告平台预测的用户对于该广告的点击概率 ，GSP 拍卖机制会根据每个广告的期望点击价值，即 ，对所有广告进行排序，并按照排序从高到低依次分配 个广告位。当一个广告赢得了第 高的广告位时，其点击之后的收费为 ，其中下标 表示排名为 的广告的期望点击价值。

GSP 拍卖对于价值最大化的广告主是满足激励兼容和个体理性的，因为它满足了两个条件，单调性（分配关于出价单调）和关键收费（收费为获得该分配所需的最小出价）。于是，GSP 拍卖中广告主的出价就等于她的真实价值 。当 GSP 机制使用的点击率 来自一个无偏的预估模型时（有各种校准算法可以用于基本的点击率预估模型，从而进一步减小点击率预估的偏差），GSP 拍卖就能够最大化期望的社会福利，即获胜的 个广告的期望点击价值之和：

这里的 是一个集合函数，输入一个集合 ，输出其中最大的 个元素值之和。

广告拍卖机制中的点击率预估模型

我们考虑两类点击率预估模型：一类是粗糙而快速的 预估模型，记为 ；另一类是精细而慢速的点击率预估模型，记为 。第一类粗糙的 预估模型 使用轻量级的机器学习模型，并且为了减小输入的规模和防止过拟合等原因，只使用广告拍卖系统所拥有的广告特征和用户特征的一部分，分别记为 和 。而精细的 预估模型 则可能是先进而复杂的深度学习模型，能够通过较大的神经网络高效利用广告系统所拥有的全部广告特征 和用户特征 。举例，比如完全的用户特征 可能包括用户的编号、用户的较长时期的广告点击行为历史，而部分的用户特征 则可能只包括用户的编号。精细的 预估模型 为了有效利用完全用户特征 中的广告点击行为历史，可能会使用序列化建模的神经网络组建，来产生丰富的用户-广告交叉特征。与 相对的粗糙 预估模型 则可能只是双塔结构（two-tower）或者是在嵌入层（embedding layer）后面加上几层全连接层。由于 和 的这些不同之处， 相较于 会消耗更长的计算时间，但是产生更准确的 预估结果。

下面我们讨论粗糙的 预估模型 和精细的 预估模型 之间的关系。假设两个模型都在同一个样本集合 上面，使用二分类任务的交叉熵损失函数进行了充分的训练。构成集合 的元素是从拍卖机制的 样本对的真实分布中独立采样而来。对于同一个广告-用户样本对对应的完全特征 和部分特征 ，两个预估模型 和 对应的输出分别会收敛到如下结果：

其中集合 表示集合 中完全特征或部分特征为 的所有元素组成的子集，带有上标 的集合比如 表示所有标签为正的样本，即发生了点击的广告-用户样本对，组成的子集。由于 ，两个 预估模型 和 对于同一个输入 （以及其对应的部分特征），所输出的点击率之间的关系可以近似表达为：

根据上式的关系，在一阶段的 GSP 拍卖中使用 和 预估模型会分别导致下式 (3a) 和 (3b) 中的期望社会福利：

两阶段广告拍卖

由于在线广告拍卖实时系统的算力和时延限制，我们无法实现上一小节所描述的一阶段 GSP 拍卖，因为针对全集 的所有广告应用精细的 预估模型 进行打分会超时。

为了在社会福利的最优性和拍卖机制的计算时间之间进行平衡，两阶段的广告拍卖机制在实践中被广泛应用。具体地，第一阶段称为粗选阶段（pre-auction stage），使用一个分配规则 ，目的是选出一个由 个广告组成的子集，即 ；第二阶段称为拍卖阶段（auction stage），以第一阶段选出的子集 作为输入，决定广告拍卖最终的广告位分配 和收费 。粗选阶段针对广告全集 ，使用一些粗糙而快速的广告评估模型，且只使用部分的广告特征 和用户特征 ；而第二阶段的拍卖因为只需要处理第一阶段输出的较小规模的集合 ，则允许使用先进而精准的 预估模型，以及完全的广告和用户特征 。

和一阶段拍卖机制设计相比，两阶段拍卖机制的设计立刻出现两个挑战。第一个挑战是如何在两阶段的拍卖机制中保证我们想要的激励兼容和个体理性两个经济学性质。第二个挑战是考虑到两阶段拍卖的解的搜索空间很大，并且耦合在一起，如何能够将两阶段的设计解耦，同时又使得两阶段协同优化拍卖机制整体的社会福利。由于 GSP 拍卖的这两个优点 1）GSP 拍卖对于价值最大化广告主而言是满足激励兼容和个体理性的，2）GSP 拍卖如果搭配精细的 预估模型则能够实现期望社会福利的最大化，我们把第二阶段的拍卖固定为 GSP 拍卖即可，因为这样做不会为两阶段拍卖的设计引入违反激励兼容和个体理性性质的因素，且也不会引入期望社会福利损失的因素。于是通过固定第二阶段拍卖为 GSP 拍卖，我们完成了两阶段设计的解耦。

下面，我们聚焦于第一阶段粗选的设计。首先，我们需要协同第一阶段的粗选和第二阶段的 GSP 拍卖，来使得两阶段整体实现激励兼容和个体理性需要的两个条件（单调性和关键收费）。由于粗选阶段只涉及分配而不涉及收费，所以我们只需要保证粗选的分配 满足单调性，即 是关于 单调的。如果做到了这点，那么两阶段整体的分配单调性就满足了，即当广告主 增加自己的出价时，她有四种情况都满足分配单调性：1）仍然不能够进入第二阶段，则分配不变；2）能够从无法进入第二阶段拍卖变为能够进入第二阶段但是仍然不能够赢得广告位，则分配不变；3）能够从无法进入第二阶段拍卖变为能够进入第二阶段并赢得广告位，则分配增加；4）本来就能够进入第二阶段，则 GSP 的分配关于出价单增。然后，我们形式化给出粗选阶段的优化目标。粗选阶段的优化问题是选出一个广告子集 交给第二阶段的 GSP 拍卖，使得两阶段拍卖的期望社会福利能够最大化。第二阶段的 GSP 拍卖在拿到粗选阶段输出的广告子集 之后，会根据其中广告的期望点击价值 排序，并选出排名最高的 个广告，记为集合 ，从而得到期望的社会福利在第一阶段的粗选中，无法获得精细的 ，并且只能够使用广告和用户的部分特征 ，所以精细的 对于粗选阶段而言可以看做随机变量。于是粗选的优化问题可以写成随机优化问题（stochastic optimization problem）：

其中， 是从所有广告的出价组成的向量 中去掉广告 的出价。

▐ 传统解法次优性分析

工业界中广泛使用的传统两阶段拍卖的解法，我们称之为贪心解法（Greedy, GDY）。GDY 在第一阶段的粗选根据候选集 中广告的粗糙期望点击价值 排序，然后选出拍卖最高的 个广告构成集合 进入第二阶段的拍卖。第二阶段拍卖使用精细的 预估模型 在集合 上执行 GSP 拍卖。然而，GDY 不是两阶段拍卖的一个适合解决方案。

对于 这种实际情况，我们可以很容易构造出例子来说明贪心解法 GDY 的次优性。例子 1 ：假设有 个广告，满足 。其中，对于 的广告有精细的预估模型和粗糙的预估模型都输出同样的 预估值，即 。而另有一个广告 （）站在粗选的视角看，在第二阶段拍卖有两种可能的 ctr 预估值：以 的概率 ，或者以 的概率 。这里 是一个足够大的值使得 成立。

贪心解法 GDY 在这个例子中会如下运行：首先在粗选阶段选择下标为 到 的广告，然后第二阶段的 GSP 会展示下标为 到 的广告。于是贪心解法 GDY 实现的期望社会福利是 。然而，如果粗选阶段选择集合包含了广告 ，比如 ，则经过第二阶段的 GSP 拍卖之后，期望的社会福利会超过 GDY 得到的期望社会福利：

在真实的在线广告拍卖场景中，常用的两阶段拍卖的贪心解法就会遇到例子 1 所抽象的这种情况：有的广告（比如例子中下标为 的广告）在粗糙预估模型 的评估下会有一个较低的预估值 ，但是可能精细的预估模型 能够利用更丰富的特征信息给出一个较高的预估值 。如果粗选阶段在决策的时候能够考虑到第二阶段的 GSP 实际上会进行更加精细的 预估，并且根据这个精细结果重新对广告集合 进行排序，那么粗选阶段能够做出更好的决策，即选择那些在精细 预估中可能有较高期望点击价值潜力的广告送入第二阶段的 GSP，从而实现两阶段整体更高的期望社会福利。注意，这个例子的构造也是满足 (2) 中描述的粗糙预估模型和精细预估模型对于同一个广告的点击率预估之间的关系，即粗选阶段可以把   给出的 看作是从均值为 的分布中进行采样的随机变量。从这个视角来看待第一阶段的粗选，则它是一个在随机变量构成的集合上的子集选择问题。这个问题的相关理论分析在“团队选择问题”（team selection）等更普遍的背景中有讨论过。

通过上述分析，我们想要传达的观察是：实践中广泛使用的贪心解法，将两阶段整体的期望社会福利最大化看做了两个阶段分别进行社会福利最大化，并在两个阶段使用同样的评估指标（粗选阶段 和拍卖阶段 ）其实会导致两阶段整体社会福利的损失。当设计一个两阶段拍卖时，我们应该考虑两个阶段之间的交互关系，即第二阶段实际上会基于第一阶段选择的子集进行更准确的预估和重新排序，所以每个阶段各自的优化问题可能会不同于整体的优化问题。我们应该找到每个阶段对应的优化问题，以及对应的评估指标，从而保证两阶段整体的优化性能。

▐ 粗选阶段设计

这一节，我们首先给出求解 (4) 中定义的粗选问题计算复杂性分析。接着，为了让减小实际场景中粗选的求解复杂性，我们针对粗选提出一个广告粒度的评估指标，使其能够大规模应用于粗选阶段的子集选择，称为粗选打分（pre-auction score, PAS）。

粗选问题的复杂性分析

我们首先证明即使将 (4) 定义的粗选问题（PA）中的关于 的单调性去掉，得到的简单版本的粗选问题（SimPA）仍然是难以求解的。

其中， 是一个随机变量，代表在粗选阶段尚未得到的第二阶段拍卖中的 输出的精细 预估值。set cover 问题可以归约到 SimPA ，说明 SimPA 是 NP-难。事实上，SimPA 问题是一个带有集合大小限制的次模最大化问题。对于我们已知的事实，两阶段拍卖粗选对应的这种次模最大化问题没有明显的易于求解且扩展性良好的解决方案：1）暴力算法需要从 的集合粒度进行评估，从而导致无法接受的 的指数时间复杂度。2）针对带集合大小限制的次模最大化问题的经典近似算法需要根据每个元素对于集合函数的边际贡献进行序列化的决策，所以不能够按照广告粒度并行评估的方法计算，在实践中的高扩展性要求下仍然不可行。3）我们强调在粗选阶段的视角下， 是尚未揭晓的随机变量，且在实践中其分布也是难以显式建模的，于是仅仅是计算目标次模函数的值也是难以实现的。即使是带限制的次模最大化问题的并行近似算法也不适合使用，因为它需要对次模函数进行求值。

考虑到在线广告两阶段拍卖粗选阶段在线上服务时的可扩展性要求，下面我们提出针对粗选阶段集合选择的广告粒度评估指标 PAS，使得我们可以并行地评价每个广告，并且避免去直接计算次模集合函数的值。为了解决 显式分布缺失的问题，我们接着提出基于学习的 PAS，即使用机器学习的算法来实现我们提出的广告粒度评估指标 PAS，从而避免显式用到 的分布。

粗选打分

由于 SimPA 是 NP-难，所以直接设计广告粒度的评估指标的希望不大。但是我们注意到，有一个和期望社会福利最大化非常相近的问题，它可以直接推导出一个广告粒度的评估指标。这个相近的问题，称它为粗选期望召回率最大化（recall maximization, PA-R），即粗选阶段选择子集 使得候选全集 中的 排在前   的广告能够被尽可能粗选阶段选中，

其中 称为真实 top K 集合，表示由 中 最高的 个广告构成的集合。

下面我们推导 PA-R 问题所直接对应的广告粒度子集选择指标，使其最大化粗选期望召回率。考虑任何一个固定的子集 ，则其对于真实 top K 集合 的期望召回率是：

上式的结论告诉我们，想最大化集合 对于 的召回率，需要最大化构成 的每个元素在 的概率，即选择 个 最大的元素。因此，我们得到了粗选阶段子集选择的广告粒度评估指标，对于每个广告 而言记为 ：

我们称这个指标为粗选打分（pre-auction score, PAS）。

根据全集真实 top 集合 的定义，以及粗选打分 PAS 在 (7) 中的定义，对于任意广告 以及所有广告的部分特征 和用户特征 和其他广告的出价 ，广告 的粗选打分 PAS 是关于其出价 单调递增的。于是，如果粗选阶段根据 PAS 来对所有广告进行排序并选择前 的广告构成 送入第二阶段的拍卖，则粗选阶段的分配 满足了单调性。于是这个粗选设计能够使得两阶段拍卖整体是激励兼容的。

基于学习的粗选打分实现

直接按照公式 (7) 计算粗选打分 PAS 需要使用分布 的显式表达，而这个显式分布可能在真实的两阶段拍卖的环境中有未知和复杂的相互依赖关系，从而难以建立和表达。为了解决这个困难，我们使用参数化的神经网络来实现基于学习的粗选打分 ，使得它产生的粗选阶段的排序能够近似由公式 (7) 中原始粗选打分 PAS 产生的排序。我们使用监督学习来确定神经网络参数化的粗选打分 的参数 。监督学习使用的样本构造如下：样本特征是 ，即候选全集 个广告的出价以及粗选能够获得的广告和用户的部分特征；其标签是一个 维向量 ，其元素为每个广告的精细期望点击价值，即 。在监督学习的离线训练过程中，我们需要有精细 预估模型 对于候选全集 中的每个广告的预估值，才能够产生标签 。但是两阶段拍卖的在线服务阶段只能够产生进入第二阶段的 集合中包含的这部分广告的 。于是在离线训练中，我们需要使用精细的 预估模型 对 这部分广告计算 。

下面讨论监督学习的损失函数。我们使用 Plackett-Luce 概率模型，一个在表达置换（permutation）分布中常用的模型，进行概率建模：假设根据 进行排序得到的置换 是从一个 Plackett-Luce 概率模型表达的分布中的采样。这个分布由 个参数 表示如下：

其中 指代排名为 的广告的下标。我们可以很容易验证上述置换的概率定义满足如下两个想要的性质：1）此概率定义是归一化的，即 ；2）置换中的 top 1 概率是 。

下面我们讨论在该概率建模下，概率分布的 个参数和 PAS 中的概率之间的排序的等价关系。引理 1：若 且 ，则 。

根据引理 1 中概率模型参数 和 PAS 在排名上面的等效性，我们使用参数 来作为基于学习的粗选打分。设神经网络的直接输出 是用于近似概率模型参数 的 logits。广告 排在 top 1 的概率由 logits 表示为：

给定一个样本集 ，我们通过最小化样本 top 1 分布和神经网络输出的 对应的参数化 top 1 分布之间的交叉熵来优化 ，于是损失函数是：

其中，上标 表示样本集合 中的第 个样本。

▐ 实验结果

我们在公开数据集和工业数据集上面对我们提出的两阶段拍卖方法进行了评估。

公开数据集设定：为了能够模拟第二阶段的 GSP 拍卖，我们使用广告和用户的完全特征 来训练深度兴趣网络（Deep Interested Networks，记为 DIN），作为第二阶段使用的精细 预估模型 ，让它产生 从而获得基于学习的粗选打分训练数据的标签 。为了能够模拟用于对比的贪心解法 GDY，我们使用广告和用户的部分特征   来训练一个由嵌入层加全连接层的网络（记为 FCN）作为 GDY 粗选阶段使用的粗糙的 预估模型 ，来让它生成 。

工业数据集设定：工业数据集来自于平台中的两阶段广告拍卖的执行贪心解法 GDY 的运行日志。注意由于贪心解法 GDY 对于价值最大化的广告主而言满足激励兼容和个体理性，所以我们可以将数据日志中记录的广告出价作为广告主内心真实的点击价值。因此，我们也可以使用数据日志中记录的出价用到其他的符合激励兼容和个体理性的两阶段拍卖机制中去模拟相应的社会福利和机制收入等计算。

评价指标

表示候选全集 中的真实 top 构成的子集，而 表示 集合中的 top ，两处拍卖指标都是精细的期望点击价值 。我们考虑相关指标相对于天花板值（一阶段精细预估的 GSP 拍卖）的比例

• 社会福利率:
• Top K 召回率:
• 收入率: 其中收入  
  下标 表示相关集合中具有第 高精细期望点击价值 的广告。

对比方法

所有基线在第二阶段拍卖都使用 GSP 拍卖，并且粗选阶段也只限定于使用和 PAS 相同的部分广告和用户的特征 。下面我们只描述各个基线的子集选择指标。

• 回归 (REGCTR)：使用精细 作为标签，使用广告和用户的部分特征 , 作为特征训练回归模型。然后使用这个回归的模型的输出乘以广告出价作为粗选排序指标。
• 回归 (REG): 使用精细期望点击价值 作为标签，使用广告和用户的部分特征 作为特征训练回归模型。使用这个回归模型的输出作为粗选排序指标。

优化结果分析

在图 2 中，我们在每个数据设定下各展示了一个两阶段拍卖实例在四种不同粗选方法下是如何工作的。以第三组图对应的 Industrial 数据设定举例，5 个广告位最终在四种方法中分别分配给了全集 中精细期望点击价值 排在如下排名的广告： (GDY)， (PAS)， (REGCTR)， (REG)。于是在这个两阶段拍卖实例中，PAS 粗选能够实现相对于 GDY，REGCTR 和 REG 而言更好的 和 。

激励兼容测试

为了测试基于学习的 PAS 实现是否能够近似满足这种粗选所需要的单调性，我们针对每个广告主的出价进行了反事实扰动测试，来看有多少测试结果违反了粗选的单调性。这种反事实扰动测试是在广告拍卖激励兼容性质测试的常用方法。极低的测试失败率说明即使没有在基于学习的 PAS 的神经网络设计中强行要求粗选打分关于广告出价单调，神经网络也能自动学到近似满足单调性要求的粗选打分。

▐ 结论

本文介绍了在线广告拍卖设计中的一个新颖的问题：设计两阶段拍卖，它包含第一阶段的粗选和第二阶段的拍卖，还涉及点击率预估模型，而优化目标是最大化广告拍卖的期望社会福利。我们展示了一种广泛使用的方法的社会福利的损失，因为它忽略了两阶段之间的关系，导致粗选阶段问题建模和评价指标不合适。我们提出对价值最大化广告主而言满足激励兼容和个体理性的两阶段拍卖设计，其中第二阶段是 GSP 拍卖，而第一阶段的集合选择使用粗选打分 PAS，一种广告粒度的评估指标。我们也给出 PAS 的基于学习的实现。在公开数据和工业数据上的实验证明了我们的方法相比广泛采用的方法在两阶段拍卖的社会福利和收入上都有更好的效果

▐ 关于我们

我们是阿里妈妈展示广告机制策略算法团队，致力于不断优化阿里展示广告技术体系，驱动业务增长，推动技术持续创新；我们不断升级工程架构以支撑阿里妈妈展示广告业务稳健&高效迭代，深挖商业化价值并优化广告主投放效果，孵化创新产品和创新商业化模式，优化广告生态健壮性；我们驱动机制升级，并已迈入 Deep Learning for Mechanisms 时代，团队创新工作发表于 KDD、WWW、ICML、CIKM、WSDM、AAMAS、AAAI 等领域知名会议。在此真诚欢迎有ML背景的同学加入我们！

投递简历邮箱（请注明-展示广告机制策略）：

[e-mail]

参考文献

• He, Xinran, et al. "Practical lessons from predicting clicks on ads at facebook." Proceedings of the eighth international workshop on data mining for online advertising. 2014.
• Wang, Zhe, et al. "Cold: Towards the next generation of pre-ranking system." arXiv preprint arXiv:2007.16122 (2020).
• Ma, Jiaqi, et al. "Off-policy learning in two-stage recommender systems." Proceedings of The Web Conference 2020. 2020.
• Hron, Jiri, et al. "On component interactions in two-stage recommender systems." Advances in Neural Information Processing Systems 34 (2021).
• Kleinberg, Jon, and Maithra Raghu. "Team performance with test scores." ACM Transactions on Economics and Computation (TEAC) 6.3-4 (2018): 1-26.
  END

也许你还想看

疯狂暗示↓↓↓↓↓↓↓